home *** CD-ROM | disk | FTP | other *** search
/ TOS Silver 2000 / TOS Silver 2000.iso / programm / MM2_DEV / S / MOS / LISTS.D < prev    next >
Encoding:
Modula Definition  |  1990-10-24  |  11.9 KB  |  311 lines
  1. DEFINITION MODULE Lists;
  2. (*$H+*)
  3.  
  4. (*
  5.  * Allgemeine Listenverwaltung.
  6.  *
  7.  * Nach 'ADTLists' aus: Dal Cin, Lutz, Risse: Programmierung in Modula-2.
  8.  *
  9.  * Erstellt 22.3.87, TT
  10.  *)
  11.  
  12. (* ----------------------------------------------------------------------------
  13.  
  14.     Listen allgemein erlauben, mehrere Datenfelder nacheinander in belie-
  15.     biger Anzahl anzulegen und selektiv wieder zu entfernen. Im Gegensatz
  16.     dazu besteht eine Tabelle aus einem einmalig anfangs zu definierenden
  17.     Speicherbereich, in dem die Daten abgelegt werden und das Ein- oder
  18.     Ausfügen nur durch aufwendiges Umkopieren möglich ist. Bei Listen wird
  19.     immer nur soviel Speicher belegt, wie Datenfelder benötigt werden.
  20.  
  21.     Die Verwaltung von Listen ist im Vergleich zu Tabellen aufwendiger.
  22.     Dieses Modul bietet dafür komfortable Funktionen.
  23.  
  24.     Eine Liste wird über eine Variable der Type 'List' angelegt und ver-
  25.     waltet. Über sie werden alle Elemente der Liste verkettet. Ist die
  26.     Liste leer, existiert nur das Wurzel-Element, das zur internen Ver-
  27.     waltung dient. Auf die Wurzel kann das Anwenderprogramm nicht zugrei-
  28.     fen. Wird die Liste um neue Elemente erweitert, sind alle Elemente
  29.     ringweise verkettet. Gestartet wird üblicherweise bei der Wurzel.
  30.     Von dort aus kann jedes Element schrittweise im Kreis erreicht werden.
  31.     Am Ende wird wieder die Wurzel erreicht. Da die Liste intern mit
  32.     Zeigern verkettet wird, ist 'List' als ein Record mit zwei Zeigern
  33.     auf eine interne Datenstruktur definiert. Das Record-Element
  34.     'List.root' zeigt immer auf die Wurzel der Liste, 'List.current' zeigt
  35.     auf das gerade bearbeitete Element der Liste. 'List.user' kann vom
  36.     Anwenderprogramm verwendet werden, um 'current' zeitweise darin zu
  37.     sichern und rückzuspeichern. 'List.user' wird von diesen Funktionen
  38.     nur Anfangs beim Erzeugen einer Liste mit 'CreateList' auf 'root'
  39.     gesetzt, danach nicht mehr verändert, es sei denn, beim Löschen eines
  40.     Elements ('RemoveEntry') war 'current' = 'user'. Dann wird 'user', wie
  41.     'current', auf den Vorgänger gesetzt.
  42.  
  43.     Da Modula-2 keine generischen Datenstukturen kennt, muβ, um beliebige
  44.     Daten als Liste verwalten zu können, das Anwenderprogramm die Daten
  45.     selbst anlegen (z.B. mit NEW oder ALLOCATE). Die Listenfunktionen
  46.     speichern nur die Adressen (Zeiger auf) die Daten. Bei Entfernen
  47.     eines Elements muβ daher nicht nur das Element aus der Liste wieder
  48.     entfernt werden (mit einer Funktion dieses Moduls) sondern auch der
  49.     Speicher für das Datum wieder freigegeben werden (z.B. mit DISPOSE
  50.     oder DEALLOCATE).
  51.  
  52.     Hinweis
  53.     -------
  54.  
  55.     In einigen Modulen des MOS werden Listen verwendet (z.B. in 'Paths',
  56.     'Loader'). Dabei werden diese Listen in der Regel durch einen
  57.     neuen TYPE definiert, welcher wiederum exportiert wird (z.B in
  58.     'Paths':  "TYPE  PathList = List (* OF PathEntry *)"). Hinter
  59.     den Definitionen erscheint dann in Klammern "OF" mit einer anderen
  60.     Type. Dies bedeutet, daß alle Listenelemente über diese Type
  61.     angesprochen werden müssen. So sind beispielsweise Funktionsergebnisse,
  62.     wie 'NextEntry' (Lists-Funktion, s.u.), die ja normalerweise einen
  63.     beliebigen ADDRESS-Typen darstellen, hier als 'PathEntry' zu verwenden
  64.     ('PathEntry' ist beispielsweise ein "POINTER TO PathStr"), damit
  65.     der korrekte Zugriff auf die Listenelemente gewährleistet ist.
  66.  
  67.  
  68.     Beispiel
  69.     --------
  70.  
  71.     Ein Liste wird erzeugt und darin drei Daten eingefügt, ausgegeben,
  72.     dann ein Element gelöscht und wieder alle Elemente ausgegeben.
  73.     Am Ende wird die gesamte Liste entfernt.
  74.  
  75.  
  76.     MODULE ListDemo;
  77.  
  78.     IMPORT InOut, Lists, Strings;
  79.  
  80.     FROM SYSTEM IMPORT ADDRESS, ADR;
  81.  
  82.     FROM Storage IMPORT ALLOCATE, DEALLOCATE;
  83.  
  84.     TYPE DataStr = ARRAY [0..20] OF CHAR;
  85.          DatenType = RECORD
  86.                        (* beliebige Datendefinition *)
  87.                        no: CARDINAL;
  88.                        s: DataStr
  89.                      END;
  90.  
  91.          Element = POINTER TO DatenType;
  92.  
  93.     VAR myList: Lists.List;
  94.         error: BOOLEAN;
  95.  
  96.     PROCEDURE stop (s: ARRAY OF CHAR);               (* Fehleranzeige *)
  97.       VAR c: CHAR;
  98.       BEGIN InOut.WriteString (s); InOut.Read (c); InOut.WriteLn END stop;
  99.  
  100.     PROCEDURE insElem (no: CARDINAL; s: ARRAY OF CHAR); (* Elem. anfügen *)
  101.       VAR elem: Element; ok: BOOLEAN;
  102.       BEGIN
  103.         NEW (elem);                                  (* Speicher anfordern *)
  104.         elem^.no:= no;                               (* Daten eintragen *)
  105.         Strings.Assign (s, elem^.s, ok);
  106.         Lists.InsertEntry (myList, elem, error); (* Elem. in Liste eintragen *)
  107.         IF error THEN stop ('Kein Speicher') END
  108.       END insElem;
  109.  
  110.     PROCEDURE showElems;                           (* Alle Elemente anzeigen *)
  111.       VAR elem: Element;
  112.       BEGIN
  113.         Lists.ResetList (myList);               (* Liste auf Anfang (Wurzel) *)
  114.         InOut.WriteString ('Alle Daten:');
  115.         InOut.WriteLn;
  116.         REPEAT
  117.           elem:= Lists.NextEntry (myList);           (* Nächstes Elem. holen *)
  118.           IF elem <> NIL THEN                        (* Wenn nicht Wurzel... *)
  119.             InOut.WriteString ('no: ');
  120.             InOut.WriteCard (elem^.no, 0);
  121.             InOut.WriteString (', s: ');
  122.             InOut.WriteString (elem^.s);             (* ... dann ausgeben    *)
  123.             InOut.WriteLn
  124.           END
  125.         UNTIL elem = NIL  (* oder: "UNTIL List.LastEntry (myList)" *)
  126.       END showElems;
  127.  
  128.     PROCEDURE checkElem (elem, txt: ADDRESS): BOOLEAN;
  129.       VAR elem0: Element; txt0: POINTER TO DataStr;
  130.       BEGIN                                               (* Elemente prüfen *)
  131.         elem0:= elem; txt0:= txt;
  132.         RETURN Strings.StrEqual (elem0^.s, txt0^)
  133.                                         (* Vergl. aktuelles 's' mit Suchtext *)
  134.       END checkElem;
  135.  
  136.     PROCEDURE search (txt: DataStr);             (* Sucht bestimmtes Element *)
  137.       VAR found: BOOLEAN;
  138.       BEGIN
  139.         Lists.ScanEntries (myList, Lists.forward, checkElem, ADR (txt), found);
  140.           (* Hiermit wird, wenn 'checkElem' fündig wird, 'current' auf *)
  141.           (* das gefundene Element gesetzt.                            *)
  142.         IF NOT found THEN stop ('Nicht gefunden.') END
  143.       END search;
  144.  
  145.     PROCEDURE removeElem;
  146.       VAR elem: Element;
  147.       BEGIN
  148.         elem:= Lists.CurrentEntry (myList); (* Akt. Element ermitteln *)
  149.         DISPOSE (elem);                     (* Speicher v. Element freigeben *)
  150.         Lists.RemoveEntry (myList, error);  (* Element aus Liste entfernen *)
  151.       END removeElem;
  152.  
  153.     PROCEDURE removeAllElems;                   (* Alle Elemente freigeben *)
  154.       BEGIN
  155.         Lists.ResetList (myList);
  156.         WHILE Lists.NextEntry (myList) <> NIL DO removeElem END;
  157.       END removeAllElems;
  158.  
  159.     VAR c: CHAR;
  160.  
  161.     BEGIN
  162.       Lists.CreateList (myList, error);               (* Liste anlegen *)
  163.       IF error THEN stop ('Kein Speicher') END;
  164.       insElem (1, 'Eins');                            (* Daten anfügen *)
  165.       insElem (2, 'Zwei');
  166.       insElem (3, 'Drei');
  167.       showElems;                                  (* Alle Elemente zeigen *)
  168.       search ('Zwei');                            (* Elem. m. 'Zwei' suchen *)
  169.       removeElem;                                 (* Dies Element entfernen *)
  170.       showElems;                                  (* Alle Elemente zeigen *)
  171.       removeAllElems;                             (* Alle Elemente entfernen *)
  172.       Lists.DeleteList (myList, error);           (* Liste entfernen *)
  173.       IF error THEN stop ('Liste nicht leer !') END;
  174.       InOut.Read (c)
  175.     END ListDemo.
  176.  
  177. ---------------------------------------------------------------------------- *)
  178.  
  179. FROM SYSTEM IMPORT ADDRESS;
  180.  
  181. TYPE    LCarrier;
  182.  
  183.         List = RECORD
  184.                  current: LCarrier;
  185.                  root   : LCarrier;
  186.                  user   : LCarrier
  187.                END;
  188.  
  189.         LCondProc = PROCEDURE ( (* entry: *) ADDRESS,
  190.                                 (* info : *) ADDRESS ): BOOLEAN;
  191.  
  192.         LDir = ( forward,  (* vorwärts  *)
  193.                  backward  (* rückwärts *) );
  194.  
  195. PROCEDURE InitList ( VAR l: List );
  196.   (*
  197.    * Initialisiert die Liste 'l', sodaß sie definierte Werte
  198.    * enthält (hierbei wird nicht, wie bei CreateList, eine Liste
  199.    * angelegt, lediglich wird ein Grundzustand hergestellt)
  200.    * Diese Funktion ist nur notwendig, wenn schon auf die Liste
  201.    * mit anderen Lists-Funktionen zugegriffen werden kann, bevor
  202.    * sie mit 'CreateList' angelegt wird.
  203.    *)
  204.  
  205. PROCEDURE CreateList ( VAR list: List; VAR error: BOOLEAN );
  206.   (*
  207.    * Erzeugt neue, leere Liste.
  208.    * 'error':= "Kein Speicher mehr frei"
  209.    *)
  210.  
  211. PROCEDURE DeleteList ( VAR list: List; VAR error: BOOLEAN );
  212.   (*
  213.    * Entfernt leere Liste.
  214.    * 'error':= "Liste ist nicht leer"
  215.    *)
  216.  
  217. PROCEDURE ResetList ( VAR list: List );
  218.   (*
  219.    * Ernennt die Wurzel (list.root) zum aktuellen Eintrag.
  220.    *)
  221.  
  222. PROCEDURE ListEmpty ( VAR list: List ): BOOLEAN;
  223.   (*
  224.    * Liefert TRUE, wenn die Liste leer ist, also keine Einträge hat.
  225.    *)
  226.  
  227. PROCEDURE InsertEntry ( VAR list: List; entry: ADDRESS; VAR error: BOOLEAN );
  228.   (*
  229.    * Fügt Eintrag hinter an aktueller Position ein; 'list.current' wird auf
  230.    * neuen Eintrag gesetzt.
  231.    * 'error':= "Kein Speicher mehr frei"
  232.    *)
  233.  
  234. PROCEDURE RemoveEntry ( VAR list: List; VAR error: BOOLEAN );
  235.   (*
  236.    * Entfernt aktuellen Eintrag. 'current' wird auf Vorgänger gesetzt.
  237.    * 'error':= "list.current zeigt auf Wurzel (=list.root)"
  238.    *)
  239.  
  240. PROCEDURE AppendEntry ( VAR list: List; entry: ADDRESS; VAR error: BOOLEAN );
  241.   (*
  242.    * Fügt Eintrag am Listenende an; 'list.current' bleibt unverändert.
  243.    * 'error':= "Kein Speicher mehr frei"
  244.    *)
  245.  
  246. PROCEDURE CurrentEntry ( VAR list: List ): ADDRESS;
  247.   (*
  248.    * Liefert aktuellen Eintrag; liefert NIL, wenn 'current'='root'.
  249.    *)
  250.  
  251. PROCEDURE NextEntry ( VAR list: List ): ADDRESS;
  252.   (*
  253.    * Liefert nächsten Eintrag, setzt 'current' darauf; liefert NIL, wenn
  254.    * 'current'='root'.
  255.    *)
  256.  
  257. PROCEDURE PrevEntry ( VAR list: List ): ADDRESS;
  258.   (*
  259.    * Liefert vorigen Eintrag, setzt 'current' darauf; liefert NIL, wenn
  260.    * 'current'='root'.
  261.    *)
  262.  
  263. PROCEDURE FindEntry ( VAR list: List; entry: ADDRESS; VAR found: BOOLEAN );
  264.   (*
  265.    * Durchsucht ganze Liste nach einem Eintrag in Vorwärtsrichtung.
  266.    * Fängt dabei hinter dem aktuellen Eintrag an.
  267.    * Wird der Eintrag gefunden, zeigt 'list.current' darauf. Sonst wird
  268.    * 'list.current' auf die Wurzel gesetzt (wie bei ResetList).
  269.    * 'found':= "Eintrag gefunden"
  270.    *)
  271.  
  272. PROCEDURE ScanEntries ( VAR list: List; dir: LDir;
  273.                         cond: LCondProc; info: ADDRESS;
  274.                         VAR found: BOOLEAN );
  275.   (*
  276.    * Durchsucht die Liste in der gewünschten Reihenfolge ('dir'), beginnend
  277.    * beim nächsten Eintrag (wie 'NextEntry').
  278.    * Dabei wird jedesmal die Prozedur 'cond' aufgerufen und ihr der aktuelle
  279.    * Eintrag übergeben. Diese Prozedur kann dann entscheiden, ob weitergesucht
  280.    * werden soll, indem sie FALSE (weiter) oder TRUE (gefunden, abbrechen)
  281.    * zurückgibt. Ihr kann, z.B. als Zeiger auf einen Vergleichswert, in 'info'
  282.    * ein Pointer übergeben werden.
  283.    * Die an 'cond' übergebene Protedur darf lokal sein!
  284.    * 'found':= "Eintrag gefunden ('cond' lieferte TRUE)"
  285.    *)
  286.  
  287. PROCEDURE EndOfList ( VAR list: List ): BOOLEAN;
  288.   (*
  289.    * Liefert TRUE, wenn 'current' = 'root' ist, also wenn der aktuelle
  290.    * Eintrag die Wurzel ist.
  291.    *)
  292.  
  293. PROCEDURE NoOfEntries ( VAR list: List ): CARDINAL;
  294.   (*
  295.    * Liefert Anzahl der vorhandenen Einträge.
  296.    *)
  297.  
  298. PROCEDURE FirstEntry ( VAR list: List ): BOOLEAN;
  299.   (*
  300.    * Liefert TRUE, wenn der Vorgänger die Wurzel ist.
  301.    *)
  302.  
  303. PROCEDURE LastEntry ( VAR list: List ): BOOLEAN;
  304.   (*
  305.    * Liefert TRUE, wenn der Nachfolger die Wurzel ist.
  306.    *)
  307.  
  308. PROCEDURE SysCreateList ( VAR list: List; VAR error: BOOLEAN );
  309.  
  310. END Lists.
  311.